package sort;

/**
 * @description: 希尔排序(n2) 或者叫缩小增量排序 效率不稳定
 * @title: ShellSort
 * @author: zp
 * @date: 2021/11/15 20:58
 */
public class ShellSort extends BaseSort {
    public static void main(String[] args) {
        int count = 10000000;
        Integer[] ints = new Integer[count];
        for (int i = 0; i < count; i++) {
            ints[i] = (int) (Math.random() * count);
        }
        long start = System.currentTimeMillis();
        sort2(ints);
        long end = System.currentTimeMillis();
        System.out.println((end - start));
    }

    /**
     * @description:希尔排序交换法
     * @author: zp
     * @date: 2021/11/16 20:50
     * @param: a
     * @return: void
     */
    public static void sort(Comparable[] a) {
        int length = a.length;
        int h = 1;
        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 计算最优步长
        while (h < length / 3) {
            h = h * 3 + 1;
        }
        //当步长大于1的时候继续缩小步长
        while (h >= 1) {
            for (int i = h; i < a.length; i++) {
                //根据步长循环遍历数据
                for (int j = i; j >= h; j -= h) {
                    //遇到小的数据交换 从大到小 使用more 判断大小
                    if (less(a[j], a[j - h])) {
                        exch(a, j, j - h);
                    }
                }
            }
            //每次都让步长减少固定频率
            h /= 3;
        }

    }

    /**
     * @description: 希尔排序位移法
     * 基本和上一个排序方法一致 只是在蒋欢元素上 当这个元素真正的找到自己的位置才进行交换
     * 如果不是就不交换
     * @author: zp
     * @date: 2021/11/16 20:48
     * @param: a
     * @return: void
     */
    public static void sort2(Comparable[] a) {
        int length = a.length;
        int h = 1;
        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ...
        while (h < length / 3) {
            h = h * 3 + 1;
        }
        while (h >= 1) {
            for (int i = h; i < a.length; i++) {
                int j = i;
                Comparable temp = a[j];
                if (less(a[j], a[j - h])) {
                    while (j - h >= 0 && less(temp, a[j - h])) {
                        a[j] = a[j - h];
                        j -= h;
                    }
                    a[j] = temp;
                }
            }
            h /= 3;
        }

    }
}
